package 算法;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Comparator;
import java.util.List;

public class 股票问题 {
}
class Solution1{
    //最长回文字符符
    public String longestPalindrome(String s){
        int len = s.length();
        int[][] dp = new int[len][len];

        char t = s.charAt(len-1);
        char t1 = s.charAt(0);
        for (int i = 0; i < len; i++){
            if(s.charAt(i) == t){
                dp[0][i] =1;
            }
            if(s.charAt(len-i-1)==t1){
                dp[i][0]=1;
            }
        }
        int max =0;
        int right = 0;
        for (int i = 1; i < len; i++) {
            char t2 = s.charAt(len-i-1);
            for (int j = 1; j < len;j++){
                if(t2 == s.charAt(j)){
                    dp[i][j] = dp[i-1][j-1]+1;
                    if(dp[i][j] > max){
                        max = dp[i][j];
                        right = j;
                    }
                }
            }
        }

        return s.substring(right-max,max);

    }
    public int[][] merge(int[][] intervals) {
        Arrays.sort(intervals, new Comparator<int[]>() {
            @Override
            public int compare(int[] ints, int[] t1) {
                if(ints[0]>t1[0]) return 1;
                if(ints[0]==t1[0]){
                    if(ints[1]>t1[1])
                    return 1;
                    else if(ints[1]==t1[1])return 0;
                }

                return -1;
            }
        });
        int left = intervals[0][0];
        int right = intervals[0][1];
        List<int[]> listNode = new ArrayList<>();
        for (int i = 1; i < intervals.length; i++) {
            if(intervals[i][0]>right){
                int[] s = new int[]{left,right};
                listNode.add(s);
                left = intervals[i][0];
                right = intervals[i][1];
            }else {
                right = Math.max(right,intervals[i][1]);
            }
        }
        int[][] res = new int[listNode.size()][2];
        for (int i = 0; i < res.length; i++) {
            int[] a = listNode.get(i);
            res[i][0] = a[0];
            res[i][1] = a[1];
        }
        return res;
    }
    //中心索引 使用前缀后缀和
    public int pivotIndex(int[] nums) {
        int topSum = 0;
        int lastSum = 0;
        for (int num : nums) {
            lastSum += num;
        }
        for (int i = 0; i < nums.length; i++) {
            lastSum -= nums[i];
            if(topSum == lastSum){
                return i;
            }
            topSum+=nums[i];
        }
        return -1;
    }
    //两次交易
    public int maxProfit(int[] prices) {
        int len = prices.length;
        //0是卖出，1是买入
        int[][][] dp = new int[len][3][2];
        dp[0][0][0] = -prices[0];
        dp[0][0][1] = 1;
        dp[1][0][0] = Math.max(dp[0][0][0],-prices[1]);
        dp[1][0][1] = dp[0][0][0]+prices[1];
        dp[1][1][0] = -prices[1]+dp[0][0][0];
        dp[1][1][1] = dp[0][0][0]+prices[1];
        dp[1][2][0] = dp[0][0][0]-prices[1];

        for (int i = 1; i < len; i++) {
            dp[i][0][0] = 0;
            dp[i][0][1] = Math.max(-prices[i],dp[i-1][0][1]);
        }
        return 1;
    }

    public int maxProfit1(int[] prices,int left,int right) {
        if(left+1>= right) return 0;

        int[] res = new int[prices.length];
        res[left] = prices[left];
        int max = 0;
        for (int i = left+1; i <= right; i++) {
            res[i] = Math.min(res[i-1],prices[i]);
            max = Math.max(max,prices[i]-res[i-1]);
        }
        return max;
    }

    public int maxProfit2(int[] prices) {
        int len = prices.length;
        int[][] dp = new int[len][3];
        //代表没有股票
        dp[0][0] = 0;
        dp[1][0] = Math.max(dp[0][0],dp[0][1]+prices[1]);
        //代表有一只股票
        dp[0][1] = -prices[0];
        dp[1][1] = Math.max(dp[0][1],dp[0][0]+prices[1]);
        //代表有两只股票
        dp[0][2] = 0;
        dp[1][2] = prices[0]+prices[1];

        for (int i = 1; i < prices.length; i++) {
            dp[i][0] = Math.max(dp[i-1][0],Math.max(dp[i-1][1]+prices[i],dp[i-1][2]+2*prices[i]));
            dp[i][1] = Math.max(dp[i-1][1],dp[i-1][0]-prices[i]);
            dp[i][2] = Math.max(dp[i-1][2],dp[i-1][1]-prices[i]);
        }
        return dp[len-1][0];
    }
}